Running Time Analysis of the (1+1)-EA for OneMax and LeadingOnes under Bit-wise Noise

摘要

In many real-world optimization problems, the objective function evaluationis subject to noise, and we cannot obtain the exact objective value.Evolutionary algorithms (EAs), a type of general-purpose randomizedoptimization algorithm, have shown able to solve noisy optimization problemswell. However, previous theoretical analyses of EAs mainly focused onnoise-free optimization, which makes the theoretical understanding largelyinsufficient. Meanwhile, the few existing theoretical studies under noise oftenconsidered the one-bit noise model, which flips a randomly chosen bit of asolution before evaluation; while in many realistic applications, several bitsof a solution can be changed simultaneously. In this paper, we study a naturalextension of one-bit noise, the bit-wise noise model, which independently flipseach bit of a solution with some probability. We analyze the running time ofthe (1+1)-EA solving OneMax and LeadingOnes under bit-wise noise for the firsttime, and derive the ranges of the noise level for polynomial andsuper-polynomial running time bounds. The analysis on LeadingOnes underbit-wise noise can be easily transferred to one-bit noise, and improves thepreviously known results. Since our analysis discloses that the (1+1)-EA can beefficient only under low noise levels, we also study whether the samplingstrategy can bring robustness to noise. We prove that using sampling cansignificantly increase the largest noise level allowing a polynomial runningtime, that is, sampling is robust to noise.